import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class MedianFinder {

    /**
     * 要始终保持数据有序，这才能去找中间值，必须使用top k算法进行解决，但具体如何使用top k呢？
     * 此时已经不再是topk了，因为k值不确定
     *
     * 解题思路：
     *  先使用暴力，排序 + 双指针，使用List存储数据*/

    public static List<Integer> list;
    public static int size;

    public MedianFinder() {
        /**
         * 初始化*/
        list = new ArrayList<>();
        size = 0;
    }
    
    public void addNum(int num) {
        /**
         * 添加元素*/
        list.add(num);
        size ++;
    }
    
    public double findMedian() {
        /**
         * 找中位数*/
        // 1 预处理
        list.sort((e1, e2) -> e1 - e2);

        // 2
        int index = size / 2;
        if(size % 2 == 0) {
            return (double)(list.get(index - 1) + list.get(index)) / 2;
        } else {
            return list.get(index);
        }
    }
}